Association Rule Mining

Association rule mining is an unsupervised machine learning technique that utilizes the APRIORI algorithm.

Rule mining can be used for uncovering associations between objects in datasets and common trends in the transactions. The most direct application is found in market basket analysis or a “Customers Also Bought” approach.

By implementing the APRIORI algorithm a list of rules are generated as an output to function as if then-scenarios regarding the objects in the set.

Dependencies

library(arules)
Warning messages:
1: package ‘arules’ was built under R version 4.2.2 
2: package ‘Matrix’ was built under R version 4.2.2 
library(arulesViz)
Warning: package ‘arulesViz’ was built under R version 4.2.2
library(datasets)

Dataset

The Groceries data set contains 30 days of real-world point-of-sale transaction data from a typical local grocery outlet. The data set comprises 9835 transactions, and the items are aggregated into 169 categories.

data("Groceries")
summary(Groceries)
transactions as itemMatrix in sparse format with
 9835 rows (elements/itemsets/transactions) and
 169 columns (items) and a density of 0.02609146 

most frequent items:
      whole milk other vegetables       rolls/buns             soda           yogurt          (Other) 
            2513             1903             1809             1715             1372            34055 

element (itemset/transaction) length distribution:
sizes
   1    2    3    4    5    6    7    8    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24 
2159 1643 1299 1005  855  645  545  438  350  246  182  117   78   77   55   46   29   14   14    9   11    4    6    1 
  26   27   28   29   32 
   1    1    1    3    1 

   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
  1.000   2.000   3.000   4.409   6.000  32.000 

includes extended item information - examples:

With itemFrequencyPlot() function we can create an item frequency bar and view the most frequent items

itemFrequencyPlot(Groceries, topN=20)

We can use inspect() function to display associations and transactions in a readable format

inspect(head(Groceries, 3))

This dataset is already in a usable state for the APRIORI algorithm, so no data preprocessing is required.

Apriori Algorithm

Basic Concepts

To better understand how the output rules are generated we will address the math that makes up the the APRIORI algorithm. The three parameters listed below align with the antecedent and consequent, left and right hand of the rules respectively. Yielding appropriate rules is dependent on establishing appropriate thresholds for each metric so it is pertinent that we know how they’re calculated and what they offer.

  • Support is a metric showing how often an item or item-set occurs. Specifically, the fraction of transactions that include the item or item-set compared to total transactions.

  • Confidence is an implication metric. Given the inclusion of a certain item or item-set, how mathematically confident are we that another specific item was bought with it. Confidence on its own can be confusing so only take it in context with the other two.

  • Lift will show the correlation of two items given a rule. It is a factor by which the occurrence of the two items as a set surpasses the probability of those items occurring together independently. Implying that the higher the lift value the higher chance the two items in question appear together. As a warning, lift should not be the only metric considered when making business decisions as it blinds the user to the directionality of the rule.

    • Lift>1 insinuates that the items appear together more often than they would randomly (positive relationship)

    • Lift<1 insinuates that the items appear together less often than they would randomly (negative relationship)

    • Lift=1 insinuates that the items appear together as often as they would randomly (no relationship)

Generating Rules

Let’s generate some initial rules, using a minimum of 0.001 support and 0.8 confidence thresholds. Also use minlen and maxlen to specify the threshold of items per rule.
These parameters can be adjusted to get different number of rules. If we want stronger rules, we increase the value of conf, for rules with higher frequency we increase the value of supp, and for more extended rules give higher value to maxlen.

initial_rules <- apriori(Groceries,
                         parameter = list(supp=0.001, conf=0.8, minlen=2, maxlen=10))
Apriori

Parameter specification:

Algorithmic control:

Absolute minimum support count: 9 

set item appearances ...[0 item(s)] done [0.00s].
set transactions ...[169 item(s), 9835 transaction(s)] done [0.01s].
sorting and recoding items ... [157 item(s)] done [0.00s].
creating transaction tree ... done [0.00s].
checking subsets of size 1 2 3 4 5 6 done [0.03s].
writing ... [410 rule(s)] done [0.00s].
creating S4 object  ... done [0.00s].
summary(initial_rules)
set of 410 rules

rule length distribution (lhs + rhs):sizes
  3   4   5   6 
 29 229 140  12 

   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
  3.000   4.000   4.000   4.329   5.000   6.000 

summary of quality measures:
    support           confidence        coverage             lift            count      
 Min.   :0.001017   Min.   :0.8000   Min.   :0.001017   Min.   : 3.131   Min.   :10.00  
 1st Qu.:0.001017   1st Qu.:0.8333   1st Qu.:0.001220   1st Qu.: 3.312   1st Qu.:10.00  
 Median :0.001220   Median :0.8462   Median :0.001322   Median : 3.588   Median :12.00  
 Mean   :0.001247   Mean   :0.8663   Mean   :0.001449   Mean   : 3.951   Mean   :12.27  
 3rd Qu.:0.001322   3rd Qu.:0.9091   3rd Qu.:0.001627   3rd Qu.: 4.341   3rd Qu.:13.00  
 Max.   :0.003152   Max.   :1.0000   Max.   :0.003559   Max.   :11.235   Max.   :31.00  

mining info:

With the inspect() function we can analyse the rules created. Let’s print the first 10

options(digits=3) #3 digits in the output
inspect(initial_rules[1:10])

From this output we can conclude that:

  • 90.5% of the time a customer buys ‘liquor and red/blush wine’ together, they also buy’bootled beer

  • Every time (100% confidence) that a customer buys ‘rice and sugar’ together, they also buy ’whole milk’

Redundant Rules

A rule is redundant if exists another rule, that is a subset (has less items) of that original rule, with the same of higher confidence.

The handy is.redundant function shows all the redundant rules

redundant_rules <- initial_rules[is.redundant(initial_rules)]

inspect(redundant_rules)
     lhs                        rhs                support confidence coverage lift count
[1]  {tropical fruit,                                                                    
      herbs,                                                                             
      other vegetables}      => {whole milk}       0.00132      0.812  0.00163 3.18    13
[2]  {hamburger meat,                                                                    
      other vegetables,                                                                  
      curd}                  => {whole milk}       0.00163      0.800  0.00203 3.13    16
[3]  {root vegetables,                                                                   
      herbs,                                                                             
      other vegetables,                                                                  
      rolls/buns}            => {whole milk}       0.00102      0.833  0.00122 3.26    10
[4]  {root vegetables,                                                                   
      other vegetables,                                                                  
      butter milk,                                                                       
      yogurt}                => {whole milk}       0.00102      0.833  0.00122 3.26    10
[5]  {tropical fruit,                                                                    
      root vegetables,                                                                   
      onions,                                                                            
      whole milk}            => {other vegetables} 0.00102      0.833  0.00122 4.31    10
[6]  {citrus fruit,                                                                      
      other vegetables,                                                                  
      cream cheese ,                                                                     
      domestic eggs}         => {whole milk}       0.00112      0.846  0.00132 3.31    11
[7]  {root vegetables,                                                                   
      whole milk,                                                                        
      whipped/sour cream,                                                                
      white bread}           => {other vegetables} 0.00112      0.846  0.00132 4.37    11
[8]  {citrus fruit,                                                                      
      other vegetables,                                                                  
      frozen vegetables,                                                                 
      fruit/vegetable juice} => {whole milk}       0.00102      0.833  0.00122 3.26    10
[9]  {beef,                                                                              
      tropical fruit,                                                                    
      whole milk,                                                                        
      whipped/sour cream}    => {other vegetables} 0.00112      0.846  0.00132 4.37    11
[10] {pip fruit,                                                                         
      other vegetables,                                                                  
      butter,                                                                            
      whipped/sour cream}    => {whole milk}       0.00132      0.867  0.00153 3.39    13
[11] {whole milk,                                                                        
      butter,                                                                            
      whipped/sour cream,                                                                
      soda}                  => {other vegetables} 0.00102      0.909  0.00112 4.70    10
[12] {citrus fruit,                                                                      
      root vegetables,                                                                   
      whole milk,                                                                        
      newspapers}            => {other vegetables} 0.00102      0.833  0.00122 4.31    10
[13] {tropical fruit,                                                                    
      root vegetables,                                                                   
      other vegetables,                                                                  
      yogurt,                                                                            
      oil}                   => {whole milk}       0.00102      1.000  0.00102 3.91    10
[14] {tropical fruit,                                                                    
      root vegetables,                                                                   
      whole milk,                                                                        
      yogurt,                                                                            
      oil}                   => {other vegetables} 0.00102      0.909  0.00112 4.70    10
[15] {beef,                                                                              
      tropical fruit,                                                                    
      root vegetables,                                                                   
      other vegetables,                                                                  
      rolls/buns}            => {whole milk}       0.00112      0.846  0.00132 3.31    11
[16] {tropical fruit,                                                                    
      other vegetables,                                                                  
      butter,                                                                            
      yogurt,                                                                            
      domestic eggs}         => {whole milk}       0.00102      0.909  0.00112 3.56    10
[17] {tropical fruit,                                                                    
      whole milk,                                                                        
      butter,                                                                            
      yogurt,                                                                            
      domestic eggs}         => {other vegetables} 0.00102      0.833  0.00122 4.31    10
[18] {tropical fruit,                                                                    
      root vegetables,                                                                   
      other vegetables,                                                                  
      butter,                                                                            
      yogurt}                => {whole milk}       0.00112      0.846  0.00132 3.31    11

Thus we can proceed to remove redundant rules from the initial set

nonredundant_rules <- initial_rules[!is.redundant(initial_rules)]

summary(nonredundant_rules)
set of 392 rules

rule length distribution (lhs + rhs):sizes
  3   4   5   6 
 29 227 130   6 

   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
   3.00    4.00    4.00    4.29    5.00    6.00 

summary of quality measures:
    support          confidence       coverage            lift           count     
 Min.   :0.00102   Min.   :0.800   Min.   :0.00102   Min.   : 3.13   Min.   :10.0  
 1st Qu.:0.00102   1st Qu.:0.833   1st Qu.:0.00122   1st Qu.: 3.31   1st Qu.:10.0  
 Median :0.00122   Median :0.846   Median :0.00132   Median : 3.59   Median :12.0  
 Mean   :0.00125   Mean   :0.867   Mean   :0.00146   Mean   : 3.96   Mean   :12.3  
 3rd Qu.:0.00132   3rd Qu.:0.909   3rd Qu.:0.00163   3rd Qu.: 4.36   3rd Qu.:13.0  
 Max.   :0.00315   Max.   :1.000   Max.   :0.00356   Max.   :11.24   Max.   :31.0  

mining info:

Visualizing Association Rules

Since there can be hundreds or thousands of rules generated based on the data, you need a couple of ways to present your findings. The arulesViz package provides a powerful function, plot(), with a variety of methods to show the rules.

Scatter-plot

A straight-forward visualization of association rules is to use a scatter plot. It uses Support and Confidence on the axes. In addition, third measure Lift is used by default to color (grey levels) of the points.

plot(nonredundant_rules, method="scatterplot", engine="plotly")
To reduce overplotting, jitter is added! Use jitter = 0 to prevent jitter.
Registered S3 method overwritten by 'data.table':
  method           from
  print.data.table     
Registered S3 method overwritten by 'htmlwidgets':
  method           from         
  print.htmlwidget tools:rstudio

Graph-based

Graph-based techniques visualize association rules using vertices and edges where vertices are labeled with item names, and item sets or rules are represented as a second set of vertices. Items are connected with item-sets/rules using directed arrows. Arrows pointing from items to rule vertices indicate LHS items and an arrow from a rule to an item indicates the RHS. The size and color of vertices often represent interest measures.

Lets plot the top 10 rules with the highest lift, to avoid congestion in the graph.

top10_rules <- head(nonredundant_rules, n=10, by="lift")

plot(top10_rules, method="graph", engine="htmlwidget")

Parallel Coordinates Plot

Represents the rules (or itemsets) as a parallel coordinate plot (from LHS to RHS).

plot(top10_rules, method="paracoord")

LS0tDQp0aXRsZTogIkFzc29jaWF0aW9uIFJ1bGVzIE1pbmluZyINCmF1dGhvcjogIkFuZHLDqSBOYXNjaW1lbnRvIg0KZGF0ZTogImByIFN5cy5EYXRlKClgIg0Kb3V0cHV0OiBodG1sX25vdGVib29rDQotLS0NCg0KIyBBc3NvY2lhdGlvbiBSdWxlIE1pbmluZw0KDQpBc3NvY2lhdGlvbiBydWxlIG1pbmluZyBpcyBhbiB1bnN1cGVydmlzZWQgbWFjaGluZSBsZWFybmluZyB0ZWNobmlxdWUgdGhhdCB1dGlsaXplcyB0aGUgQVBSSU9SSSBhbGdvcml0aG0uXA0KXA0KUnVsZSBtaW5pbmcgY2FuIGJlIHVzZWQgZm9yIHVuY292ZXJpbmcgYXNzb2NpYXRpb25zIGJldHdlZW4gb2JqZWN0cyBpbiBkYXRhc2V0cyBhbmQgY29tbW9uIHRyZW5kcyBpbiB0aGUgdHJhbnNhY3Rpb25zLiBUaGUgbW9zdCBkaXJlY3QgYXBwbGljYXRpb24gaXMgZm91bmQgaW4gbWFya2V0IGJhc2tldCBhbmFseXNpcyBvciBhICJDdXN0b21lcnMgQWxzbyBCb3VnaHQiIGFwcHJvYWNoLlwNClwNCkJ5IGltcGxlbWVudGluZyB0aGUgQVBSSU9SSSBhbGdvcml0aG0gYSBsaXN0IG9mIHJ1bGVzIGFyZSBnZW5lcmF0ZWQgYXMgYW4gb3V0cHV0IHRvIGZ1bmN0aW9uIGFzIGlmIHRoZW4tc2NlbmFyaW9zIHJlZ2FyZGluZyB0aGUgb2JqZWN0cyBpbiB0aGUgc2V0Lg0KDQojIyMjICoqU291cmNlczoqKg0KDQo8aHR0cHM6Ly9tZWRpdW0uY29tL3N3bGgvYXNzb2NpYXRpb24tcnVsZS1taW5pbmctaW4tci1hY2JkMTVlMGRlODk+XA0KPGh0dHBzOi8vcnB1YnMuY29tL2FydTA1MTEvR3JvY2VyaWVzRGF0YXNldEFzc29jaWF0aW9uQW5hbHlzaXM+XA0KPGh0dHBzOi8vd3d3LmRhdGFjYW1wLmNvbS90dXRvcmlhbC9tYXJrZXQtYmFza2V0LWFuYWx5c2lzLXI+XA0KPGh0dHBzOi8vd3d3LmtpcmVuei5jb20vcG9zdC8yMDIwLTA1LTE0LXItYXNzb2NpYXRpb24tcnVsZS1taW5pbmc+DQoNCiMjIERlcGVuZGVuY2llcw0KDQpgYGB7cn0NCmxpYnJhcnkoYXJ1bGVzKQ0KbGlicmFyeShhcnVsZXNWaXopDQpsaWJyYXJ5KGRhdGFzZXRzKQ0KYGBgDQoNCiMjIERhdGFzZXQNCg0KVGhlIEdyb2NlcmllcyBkYXRhIHNldCBjb250YWlucyAzMCBkYXlzIG9mIHJlYWwtd29ybGQgcG9pbnQtb2Ytc2FsZSB0cmFuc2FjdGlvbiBkYXRhIGZyb20gYSB0eXBpY2FsIGxvY2FsIGdyb2Nlcnkgb3V0bGV0LiBUaGUgZGF0YSBzZXQgY29tcHJpc2VzIDk4MzUgdHJhbnNhY3Rpb25zLCBhbmQgdGhlIGl0ZW1zIGFyZSBhZ2dyZWdhdGVkIGludG8gMTY5IGNhdGVnb3JpZXMuDQoNCmBgYHtyfQ0KZGF0YSgiR3JvY2VyaWVzIikNCmBgYA0KDQpgYGB7cn0NCnN1bW1hcnkoR3JvY2VyaWVzKQ0KYGBgDQoNCldpdGggYGl0ZW1GcmVxdWVuY3lQbG90KClgIGZ1bmN0aW9uIHdlIGNhbiBjcmVhdGUgYW4gaXRlbSBmcmVxdWVuY3kgYmFyIGFuZCB2aWV3IHRoZSBtb3N0IGZyZXF1ZW50IGl0ZW1zDQoNCmBgYHtyfQ0KaXRlbUZyZXF1ZW5jeVBsb3QoR3JvY2VyaWVzLCB0b3BOPTIwKQ0KYGBgDQoNCldlIGNhbiB1c2UgYGluc3BlY3QoKWAgZnVuY3Rpb24gdG8gZGlzcGxheSBhc3NvY2lhdGlvbnMgYW5kIHRyYW5zYWN0aW9ucyBpbiBhIHJlYWRhYmxlIGZvcm1hdA0KDQpgYGB7cn0NCmluc3BlY3QoaGVhZChHcm9jZXJpZXMsIDMpKQ0KYGBgDQoNClRoaXMgZGF0YXNldCBpcyBhbHJlYWR5IGluIGEgdXNhYmxlIHN0YXRlIGZvciB0aGUgQVBSSU9SSSBhbGdvcml0aG0sIHNvIG5vIGRhdGEgcHJlcHJvY2Vzc2luZyBpcyByZXF1aXJlZC4NCg0KIyMgQXByaW9yaSBBbGdvcml0aG0NCg0KIyMjIEJhc2ljIENvbmNlcHRzDQoNClRvIGJldHRlciB1bmRlcnN0YW5kIGhvdyB0aGUgb3V0cHV0IHJ1bGVzIGFyZSBnZW5lcmF0ZWQgd2Ugd2lsbCBhZGRyZXNzIHRoZSBtYXRoIHRoYXQgbWFrZXMgdXAgdGhlIHRoZSBBUFJJT1JJIGFsZ29yaXRobS4gVGhlIHRocmVlIHBhcmFtZXRlcnMgbGlzdGVkIGJlbG93IGFsaWduIHdpdGggdGhlIGFudGVjZWRlbnQgYW5kIGNvbnNlcXVlbnQsIGxlZnQgYW5kIHJpZ2h0IGhhbmQgb2YgdGhlIHJ1bGVzIHJlc3BlY3RpdmVseS4gWWllbGRpbmcgYXBwcm9wcmlhdGUgcnVsZXMgaXMgZGVwZW5kZW50IG9uIGVzdGFibGlzaGluZyBhcHByb3ByaWF0ZSB0aHJlc2hvbGRzIGZvciBlYWNoIG1ldHJpYyBzbyBpdCBpcyBwZXJ0aW5lbnQgdGhhdCB3ZSBrbm93IGhvdyB0aGV5J3JlIGNhbGN1bGF0ZWQgYW5kIHdoYXQgdGhleSBvZmZlci4NCg0KIVtdKGltYWdlcy9wYXN0ZS05Q0IzMUE2RS5wbmcpe3dpZHRoPSIzNzkifQ0KDQotICAgKipTdXBwb3J0KiogaXMgYSBtZXRyaWMgc2hvd2luZyBob3cgb2Z0ZW4gYW4gaXRlbSBvciBpdGVtLXNldCBvY2N1cnMuIFNwZWNpZmljYWxseSwgdGhlIGZyYWN0aW9uIG9mIHRyYW5zYWN0aW9ucyB0aGF0IGluY2x1ZGUgdGhlIGl0ZW0gb3IgaXRlbS1zZXQgY29tcGFyZWQgdG8gdG90YWwgdHJhbnNhY3Rpb25zLg0KDQotICAgKipDb25maWRlbmNlKiogaXMgYW4gaW1wbGljYXRpb24gbWV0cmljLiBHaXZlbiB0aGUgaW5jbHVzaW9uIG9mIGEgY2VydGFpbiBpdGVtIG9yIGl0ZW0tc2V0LCBob3cgbWF0aGVtYXRpY2FsbHkgY29uZmlkZW50IGFyZSB3ZSB0aGF0IGFub3RoZXIgc3BlY2lmaWMgaXRlbSB3YXMgYm91Z2h0IHdpdGggaXQuIENvbmZpZGVuY2Ugb24gaXRzIG93biBjYW4gYmUgY29uZnVzaW5nIHNvIG9ubHkgdGFrZSBpdCBpbiBjb250ZXh0IHdpdGggdGhlIG90aGVyIHR3by4NCg0KLSAgICoqTGlmdCoqIHdpbGwgc2hvdyB0aGUgY29ycmVsYXRpb24gb2YgdHdvIGl0ZW1zIGdpdmVuIGEgcnVsZS4gSXQgaXMgYSBmYWN0b3IgYnkgd2hpY2ggdGhlIG9jY3VycmVuY2Ugb2YgdGhlIHR3byBpdGVtcyBhcyBhIHNldCBzdXJwYXNzZXMgdGhlIHByb2JhYmlsaXR5IG9mIHRob3NlIGl0ZW1zIG9jY3VycmluZyB0b2dldGhlciBpbmRlcGVuZGVudGx5LiBJbXBseWluZyB0aGF0IHRoZSBoaWdoZXIgdGhlIGxpZnQgdmFsdWUgdGhlIGhpZ2hlciBjaGFuY2UgdGhlIHR3byBpdGVtcyBpbiBxdWVzdGlvbiBhcHBlYXIgdG9nZXRoZXIuIEFzIGEgd2FybmluZywgbGlmdCBzaG91bGQgbm90IGJlIHRoZSBvbmx5IG1ldHJpYyBjb25zaWRlcmVkIHdoZW4gbWFraW5nIGJ1c2luZXNzIGRlY2lzaW9ucyBhcyBpdCBibGluZHMgdGhlIHVzZXIgdG8gdGhlIGRpcmVjdGlvbmFsaXR5IG9mIHRoZSBydWxlLg0KDQogICAgLSAgICoqKkxpZnRcPjEqKiogaW5zaW51YXRlcyB0aGF0IHRoZSBpdGVtcyBhcHBlYXIgdG9nZXRoZXIgbW9yZSBvZnRlbiB0aGFuIHRoZXkgd291bGQgcmFuZG9tbHkgKHBvc2l0aXZlIHJlbGF0aW9uc2hpcCkNCg0KICAgIC0gICAqKipMaWZ0XDwxKioqIGluc2ludWF0ZXMgdGhhdCB0aGUgaXRlbXMgYXBwZWFyIHRvZ2V0aGVyIGxlc3Mgb2Z0ZW4gdGhhbiB0aGV5IHdvdWxkIHJhbmRvbWx5IChuZWdhdGl2ZSByZWxhdGlvbnNoaXApDQoNCiAgICAtICAgKioqTGlmdD0xKioqIGluc2ludWF0ZXMgdGhhdCB0aGUgaXRlbXMgYXBwZWFyIHRvZ2V0aGVyIGFzIG9mdGVuIGFzIHRoZXkgd291bGQgcmFuZG9tbHkgKG5vIHJlbGF0aW9uc2hpcCkNCg0KIyMjIEdlbmVyYXRpbmcgUnVsZXMNCg0KTGV0J3MgZ2VuZXJhdGUgc29tZSBpbml0aWFsIHJ1bGVzLCB1c2luZyBhIG1pbmltdW0gb2YgMC4wMDEgKnN1cHBvcnQqIGFuZCAwLjggKmNvbmZpZGVuY2UqIHRocmVzaG9sZHMuIEFsc28gdXNlICptaW5sZW4qIGFuZCAqbWF4bGVuKiB0byBzcGVjaWZ5IHRoZSB0aHJlc2hvbGQgb2YgaXRlbXMgcGVyIHJ1bGUuXA0KVGhlc2UgcGFyYW1ldGVycyBjYW4gYmUgYWRqdXN0ZWQgdG8gZ2V0IGRpZmZlcmVudCBudW1iZXIgb2YgcnVsZXMuIElmIHdlIHdhbnQgc3Ryb25nZXIgcnVsZXMsIHdlIGluY3JlYXNlIHRoZSB2YWx1ZSBvZiAqY29uZiwqIGZvciBydWxlcyB3aXRoIGhpZ2hlciBmcmVxdWVuY3kgd2UgaW5jcmVhc2UgdGhlIHZhbHVlIG9mICpzdXBwKiwgYW5kIGZvciBtb3JlIGV4dGVuZGVkIHJ1bGVzIGdpdmUgaGlnaGVyIHZhbHVlIHRvICptYXhsZW4uKg0KDQpgYGB7cn0NCmluaXRpYWxfcnVsZXMgPC0gYXByaW9yaShHcm9jZXJpZXMsDQogICAgICAgICAgICAgICAgICAgICAgICAgcGFyYW1ldGVyID0gbGlzdChzdXBwPTAuMDAxLCBjb25mPTAuOCwgbWlubGVuPTIsIG1heGxlbj0xMCkpDQpgYGANCg0KYGBge3J9DQpzdW1tYXJ5KGluaXRpYWxfcnVsZXMpDQpgYGANCg0KV2l0aCB0aGUgYGluc3BlY3QoKWAgZnVuY3Rpb24gd2UgY2FuIGFuYWx5c2UgdGhlIHJ1bGVzIGNyZWF0ZWQuIExldCdzIHByaW50IHRoZSBmaXJzdCAxMA0KDQpgYGB7cn0NCm9wdGlvbnMoZGlnaXRzPTMpICMzIGRpZ2l0cyBpbiB0aGUgb3V0cHV0DQppbnNwZWN0KGluaXRpYWxfcnVsZXNbMToxMF0pDQpgYGANCg0KRnJvbSB0aGlzIG91dHB1dCB3ZSBjYW4gY29uY2x1ZGUgdGhhdDoNCg0KLSAgIDkwLjUlIG9mIHRoZSB0aW1lIGEgY3VzdG9tZXIgYnV5cyAnKmxpcXVvciogYW5kICpyZWQvYmx1c2ggd2luZScqIHRvZ2V0aGVyLCB0aGV5IGFsc28gYnV5Jypib290bGVkIGJlZXIqJw0KDQotICAgRXZlcnkgdGltZSAoMTAwJSBjb25maWRlbmNlKSB0aGF0IGEgY3VzdG9tZXIgYnV5cyAnKnJpY2UqIGFuZCAqc3VnYXInKiB0b2dldGhlciwgdGhleSBhbHNvIGJ1eSAnd2hvbGUgbWlsaycNCg0KIyMjIFJlZHVuZGFudCBSdWxlcw0KDQpBIHJ1bGUgaXMgcmVkdW5kYW50IGlmIGV4aXN0cyBhbm90aGVyIHJ1bGUsIHRoYXQgaXMgYSBzdWJzZXQgKGhhcyBsZXNzIGl0ZW1zKSBvZiB0aGF0IG9yaWdpbmFsIHJ1bGUsIHdpdGggdGhlIHNhbWUgb2YgaGlnaGVyIGNvbmZpZGVuY2UuDQoNClRoZSBoYW5keSBgaXMucmVkdW5kYW50YCBmdW5jdGlvbiBzaG93cyBhbGwgdGhlIHJlZHVuZGFudCBydWxlcw0KDQpgYGB7cn0NCnJlZHVuZGFudF9ydWxlcyA8LSBpbml0aWFsX3J1bGVzW2lzLnJlZHVuZGFudChpbml0aWFsX3J1bGVzKV0NCg0KaW5zcGVjdChyZWR1bmRhbnRfcnVsZXMpDQpgYGANCg0KVGh1cyB3ZSBjYW4gcHJvY2VlZCB0byByZW1vdmUgcmVkdW5kYW50IHJ1bGVzIGZyb20gdGhlIGluaXRpYWwgc2V0DQoNCmBgYHtyfQ0Kbm9ucmVkdW5kYW50X3J1bGVzIDwtIGluaXRpYWxfcnVsZXNbIWlzLnJlZHVuZGFudChpbml0aWFsX3J1bGVzKV0NCg0Kc3VtbWFyeShub25yZWR1bmRhbnRfcnVsZXMpDQpgYGANCg0KIyMjIEZpbmRpbmcgcnVsZXMgcmVsYXRlZCB0byBnaXZlbiBpdGVtcw0KDQpTb21ldGltZXMsIHdlIHdhbnQgdG8gd29yayBvbiBhIHNwZWNpZmljIHByb2R1Y3QuIElmIHdlIHdhbnQgdG8gZmluZCBvdXQgd2hhdCBjYXVzZXMgaW5mbHVlbmNlIG9uIHRoZSBwdXJjaGFzZSBvZiBpdGVtIFggd2UgY2FuIHVzZSAqYXBwZWFyYW5jZSogb3B0aW9uIGluIHRoZSBgYXByaW9yaWAgY29tbWFuZC4gKmFwcGVhcmFuY2UqIGdpdmVzIHVzIG9wdGlvbnMgdG8gc2V0ICoqTEhTIChJRiBwYXJ0KSoqIGFuZCAqKlJIUyAoVEhFTiBwYXJ0KSoqIG9mIHRoZSBydWxlLg0KDQojIyMjIFJIUw0KDQpGb3IgZXhhbXBsZSwgdG8gYW5hbHl6ZSB3aGF0IGl0ZW1zIGN1c3RvbWVycyBidXkgYmVmb3JlIGJ1eWluZyAneW9ndXJ0JyB3ZSBjYW4gZGVmaW5lICpyaHMqIGluIHRoZSAqYXBwZWFyYW5jZSogb3B0aW9uLg0KDQpgYGB7cn0NCnlvZ3VydF9yaHNfcnVsZXMgPC0gYXByaW9yaShHcm9jZXJpZXMsDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgcGFyYW1ldGVyID0gbGlzdChzdXBwPTAuMDAxLCBjb25mPTAuOCwNCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIG1pbmxlbj0yLCBtYXhsZW49MTApLA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgIGFwcGVhcmFuY2UgPSBsaXN0KGRlZmF1bHQ9ImxocyIsIHJocz0ieW9ndXJ0IikpDQoNCmluc3BlY3QoeW9ndXJ0X3Joc19ydWxlc1sxOjEwXSkNCmBgYA0KDQojIyMjIExIUw0KDQpTaW1pbGFybHksIHRvIGZpbmQgdGhlIGFuc3dlciB0byB0aGUgcXVlc3Rpb24gIipDdXN0b21lcnMgd2hvIGJvdWdodCAneW9ndXJ0JyBhbHNvIGJvdWdodC4uLi4iKiB3ZSBkZWZpbmUgdGhlICpsaHMuKg0KDQpgYGB7cn0NCnlvZ3VydF9saHNfcnVsZXMgPC0gYXByaW9yaShHcm9jZXJpZXMsDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgcGFyYW1ldGVyID0gbGlzdChzdXBwPTAuMDAxLCBjb25mPTAuMTUsDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBtaW5sZW49MiwgbWF4bGVuPTEwKSwNCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBhcHBlYXJhbmNlID0gbGlzdChkZWZhdWx0PSJyaHMiLCBsaHM9InlvZ3VydCIpKQ0KDQppbnNwZWN0KHlvZ3VydF9saHNfcnVsZXMpDQpgYGANCg0KIyMjIFZpc3VhbGl6aW5nIEFzc29jaWF0aW9uIFJ1bGVzDQoNClNpbmNlIHRoZXJlIGNhbiBiZSBodW5kcmVkcyBvciB0aG91c2FuZHMgb2YgcnVsZXMgZ2VuZXJhdGVkIGJhc2VkIG9uIHRoZSBkYXRhLCB5b3UgbmVlZCBhIGNvdXBsZSBvZiB3YXlzIHRvIHByZXNlbnQgeW91ciBmaW5kaW5ncy4gVGhlICphcnVsZXNWaXoqIHBhY2thZ2UgcHJvdmlkZXMgYSBwb3dlcmZ1bCBmdW5jdGlvbiwgYHBsb3QoKWAsIHdpdGggYSB2YXJpZXR5IG9mIG1ldGhvZHMgdG8gc2hvdyB0aGUgcnVsZXMuDQoNCiMjIyMgU2NhdHRlci1wbG90DQoNCkEgc3RyYWlnaHQtZm9yd2FyZCB2aXN1YWxpemF0aW9uIG9mIGFzc29jaWF0aW9uIHJ1bGVzIGlzIHRvIHVzZSBhIHNjYXR0ZXIgcGxvdC4gSXQgdXNlcyAqU3VwcG9ydCogYW5kICpDb25maWRlbmNlKiBvbiB0aGUgYXhlcy4gSW4gYWRkaXRpb24sIHRoaXJkIG1lYXN1cmUgKkxpZnQqIGlzIHVzZWQgYnkgZGVmYXVsdCB0byBjb2xvciAoZ3JleSBsZXZlbHMpIG9mIHRoZSBwb2ludHMuDQoNCmBgYHtyfQ0KcGxvdChub25yZWR1bmRhbnRfcnVsZXMsIG1ldGhvZD0ic2NhdHRlcnBsb3QiLCBlbmdpbmU9InBsb3RseSIpDQpgYGANCg0KIyMjIyBHcmFwaC1iYXNlZA0KDQpHcmFwaC1iYXNlZCB0ZWNobmlxdWVzIHZpc3VhbGl6ZSBhc3NvY2lhdGlvbiBydWxlcyB1c2luZyB2ZXJ0aWNlcyBhbmQgZWRnZXMgd2hlcmUgdmVydGljZXMgYXJlIGxhYmVsZWQgd2l0aCBpdGVtIG5hbWVzLCBhbmQgaXRlbSBzZXRzIG9yIHJ1bGVzIGFyZSByZXByZXNlbnRlZCBhcyBhIHNlY29uZCBzZXQgb2YgdmVydGljZXMuIEl0ZW1zIGFyZSBjb25uZWN0ZWQgd2l0aCBpdGVtLXNldHMvcnVsZXMgdXNpbmcgZGlyZWN0ZWQgYXJyb3dzLiBBcnJvd3MgcG9pbnRpbmcgZnJvbSBpdGVtcyB0byBydWxlIHZlcnRpY2VzIGluZGljYXRlIExIUyBpdGVtcyBhbmQgYW4gYXJyb3cgZnJvbSBhIHJ1bGUgdG8gYW4gaXRlbSBpbmRpY2F0ZXMgdGhlIFJIUy4gVGhlIHNpemUgYW5kIGNvbG9yIG9mIHZlcnRpY2VzIG9mdGVuIHJlcHJlc2VudCBpbnRlcmVzdCBtZWFzdXJlcy4NCg0KTGV0cyBwbG90IHRoZSB0b3AgMTAgcnVsZXMgd2l0aCB0aGUgaGlnaGVzdCBsaWZ0LCB0byBhdm9pZCBjb25nZXN0aW9uIGluIHRoZSBncmFwaC4NCg0KYGBge3J9DQp0b3AxMF9ydWxlcyA8LSBoZWFkKG5vbnJlZHVuZGFudF9ydWxlcywgbj0xMCwgYnk9ImxpZnQiKQ0KDQpwbG90KHRvcDEwX3J1bGVzLCBtZXRob2Q9ImdyYXBoIiwgZW5naW5lPSJodG1sd2lkZ2V0IikNCmBgYA0KDQojIyMjIFBhcmFsbGVsIENvb3JkaW5hdGVzIFBsb3QNCg0KUmVwcmVzZW50cyB0aGUgcnVsZXMgKG9yIGl0ZW1zZXRzKSBhcyBhIHBhcmFsbGVsIGNvb3JkaW5hdGUgcGxvdCAoZnJvbSBMSFMgdG8gUkhTKS4NCg0KYGBge3J9DQpwbG90KHRvcDEwX3J1bGVzLCBtZXRob2Q9InBhcmFjb29yZCIpDQpgYGANCg==